#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

//560.和为K的子数组
int subarraySum(vector<int>& nums,int k){
    //前缀和思想，sum[i]表示[0,i]的前缀和
    //统计i位置之前有多少个sum-k的子数组，就有多少个k的子数组

    unordered_map<int, int> hash;
    //先将<0,1>存放到哈希表中
    hash[0] = 1;

    int sum = 0, ret = 0;
    for(auto x : nums){
        //先求出i位置的前缀和
        sum += x;

        //再查找[0,i-1]区间有没有sum-k长度的子数组
        if(hash.count(sum-k)){
            ret += hash[sum - k];
        }

        //最后再将i位置的前缀和存放到哈希表中
        hash[sum]++;
    }

    return ret;
}


//974.和可被k整除的子数组
int subarraysDivByK(vector<int>& nums,int k){
    //前缀和思想，同余定理
    //统计i位置前有多少个前缀和余数=(sum%k+k)%k

    unordered_map<int, int> hash;

    hash[0] = 1;

    int sum = 0,rem=0, ret = 0;

    //4,5,0,-2,-3,1
    for(auto x : nums){
        sum+=x;
        rem = (sum % k + k) % k;

        if(hash.count(rem)){
            ret += hash[rem];
        }

        hash[rem]++;
    }

    return ret;
}

int main(){
    int k=0;
    vector<int> nums = {};

    int ret = subarraySum(nums);
    cout << ret;
    return 0;
}